The Mysterious Query Complexity of Tarski Fixed Points
September 17, 2025 (GHC 8102)
Tarski's fixed point theorem has extensive applications across many fields, including verification, semantics, game theory, and economics. Recently, the complexity of finding a Tarski fixed point has attracted significant attention.
In this talk, I will introduce the problem of computing a Tarski fixed point over a grid $[N]^d$, highlight our recent progress toward a better understanding of it, and discuss the surprising journey and the mysteries surrounding its complexity.
Based on joint work with Xi Chen and Mihalis Yannakakis.